![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
NIST, the National Institute of Standards and Technology, is replacing the DES encryption algorithm. The new algorithm will be called AES (Advanced Encryption Standard), will have a longer key length (128-, 192-, and 256-bit) and a larger block size (128-bit), be faster than triple DES (and probably DES), and hopefully will remain strong for a long, long time.
The process is an interesting one. In 1997, NIST sent out a request for candidate algorithms. They received fifteen submissions by the June 1998 deadline, five from the U.S. and ten from other countries. In the weeks that followed, most of the submitters posted their algorithms on the World Wide Web. In August 1998, all the submitters presented their algorithms to the world at the First AES Candidate Conference.
There will be a Second AES Candidate Conference in Rome in March 1999, where people will present papers analyzing the algorithms. Through June 1999, NIST is soliciting public comment. Then NIST will choose about five algorithms to go into the second round and, after another comment period and a third conference (sometime in mid-2000), they will choose one to turn into the standard. Then, NIST will write a FIPS, a Federal Information Processing Standard for the new algorithm, and hopefully the AES will be adopted by other standards bodies throughout the world.
All fifteen algorithms are new. Existing ones, like triple-DES, IDEA, RC5, and Blowfish, were not eligible because their block sizes were too small was not eligible because its block and key size were both too small.
The NSA did not submit any algorithm. They had one ready, but NIST preferred to use them as an independent evaluator. Of course, their classified analysis will not be made public, but NIST hopes that the public comments will recommend the same algorithms that the NSAs analysis does.
NIST required that all submitters state that if their algorithm was chosen as AES, they would give up all patent rights. Some submitters have given up patent rights regardless, others are holding on to their patent rights until they are chosen (and will keep them if they axe not chosen). Some people chose not to submit their algorithms under these circumstances, stating that they do not want to give up the ability to charge for their algorithms. But since NIST received some very high-quality designs from groups that were willing to give them away for free, it seems NIST was correct in demanding patent-free submissions.
Cryptographers are busily analyzing the submissions for security. Its tempting to think of the process as a big demolition derby: everyone submits their algorithms and then attacks all the others . . . the last one standing wins. Really, it wont be like that.
At the time of writing (November 1998), there has been some pretty devastating cryptanalysis against three of the weaker candidates. (One was broken minutes after it was presented.) By the end of the first comment period, we expect there to be weaknesses found in only a few others. We strongly believe that at the end of the process most of the candidates will be unbroken. The winner will be chosen based on other factors: performance, flexibility, suitability.
AES will have to work in a variety of current and future applications, doing all sorts of different encryption tasks. Specifically:
Choosing a single algorithm for all these applications is not easy, but thats what we have to do. It might make more sense to have a family of algorithms, each tuned to a particular application, but there will be only one AES. And when AES becomes a standard, customers will want their encryption products to be buzzword compliant. Theyll demand it in hardware, in desktop computer software, on smart cards, in electronic-commerce terminals, and in other places we never thought it would be used. Anything we pick for AES has to work in all those applications.
We designed Twofish with this in mind. Its the fastest submission on the Pentium, second fastest on the Pentium Pro/Pentium 11, efficient on RAM-poor smart cards (some other algorithms cant even fit on some smart cards), implementable in hardware at either high speeds or low gate count, and suitable to be used in a hash function. Its flexible enough for implementations where one key encrypts megabytes, and for implementations where the key changes with each block.
For more information on the AES process, visit the NIST AES home page at http://www.nist.gov/slash aes. A general performance comparison of all the AES candidates can be found at http: //www.counterpane.com/aes-performance.html [SKW+99a]; see also Brian Gladmans work at http://www. seven77.demon.co.uk/aes.htm. For a summary of the most recent attacks against the different candidates, see Lars Knudsens summary at http://www.ii.uib.no/~larsr/aes.html.
This book contains all the details about Twofish, from the design criteria to the best cryptanalysis at the time of writing (November 1998). It is based on the original Twofish AES submission [SKW+98a], but also includes the first three Twofish Technical Reports [Fer98b, WW98, WS98] and the various Twofish articles and papers [SKW+98b, Sch98, SKW+99b].
This book does not contain information about the other fourteen AES submissions, or any comparisons of Twofish with them. Since this book is about the design of Twofish, which was completed without seeing the other AES submissions (except for LOKI97 and a preliminary version of Serpent, which were published early), we felt that it would be inappropriate to discuss the other submissions in this book.
As analysis progresses, more will become known about Twofish. The latest information can always be found on the Twofish web site:
http://www.counterpane.com/twofish.html
The web site also contains downloadable Twofish source code:
Additional implementations will be added when they become available.
The authors would like to thank Carl Ellison, Nina Fefferman, Paul and Randy Milbert, who read and commented on drafts of the original AES submission, and Beth Riedman, who copyedited the manuscript twice (both the original AES submission and this book). Additionally, the authors would like to thank NIST for initiating the AES process, Miles Smid, Jim Foti, and Ed Roback for putting up with a never-ending stream of questions and complaints about its details, and all the other AES candidates for submitting their algorithms, and making the AES selection process so interesting. We know how much effort they all went through.
This work has been funded by Counterpane Systems and Hi/fn Inc.
Previous | Table of Contents | Next |